import sys
from collections import defaultdict

user_key = defaultdict(list)
key_count = defaultdict(int)
common_keys = {}

num_items = 6095
max_num_keys = 1 << 30

def analyze_keyw(fname):
    for line in open(fname):
        uid, keyw = line.strip().split()
        keyw = map(lambda s: s.split(':'), keyw.split(';'))
        keyw = map(lambda (fid, v): (int(fid), float(v)), keyw)
        uid = int(uid)
        user_key[uid] = keyw

        for k, w in keyw:
            key_count[k] += 1


    key_list = key_count.keys()
    key_list.sort(key=lambda k: -key_count[k])
    cc = 0
    for k in key_list[0:max_num_keys]:
        if key_count[k] >= 100:
            common_keys[k] = cc
            cc += 1

    # print 'common keys:', common_keys
    
def process_keyw():
    for uid in user_key:
        keyw = user_key[uid]
        ckeyw = []
        tot_w = 0.0
        for k, w in keyw:
            if k in common_keys:
                ckeyw.append((common_keys[k], w))
                tot_w += w ** 2
        if ckeyw:
            tot_w = tot_w ** 0.5
            user_key[uid] = map(lambda x: (x[0], x[1] / tot_w), ckeyw)
        else:
            user_key[uid] = []

def print_features(ofile, features, offset = 0):
    if not features:
        ofile.write('0\n')
    else:
        for t in features:
            assert t[0] < len(common_keys)
        desc = map(lambda (fid, v): '%d:%.4f' % (fid + offset, v), features)
        ofile.write('%d %s\n' % (len(features), ' '.join(desc)))
        

if __name__ == '__main__':
    if len(sys.argv) < 4:
        print 'usage: <ukeyw> <train.group> <ukeyimfb> [max_num_keys]'
        sys.exit(1)

    if len(sys.argv) >= 5:
        max_num_keys = int(sys.argv[4])

    
    analyze_keyw(sys.argv[1])
    process_keyw()

    ukey_imfb = open(sys.argv[3],"w")
    ukey_imfb.write('%d\n' % len(common_keys))

    last_user = -1
    for line in open(sys.argv[2]):
        uid, iid, r, t = map(int, line.split())
        if last_user != uid:
            print_features(ukey_imfb, user_key[uid], 0)
        last_user = uid

    ukey_imfb.close()
        
        
